算法

您所在的位置:网站首页 反转链表 k个一组 算法

算法

2023-07-13 13:10| 来源: 网络整理| 查看: 265

题目

给出一个链表,每 k 个节点一组进行翻转,并返回翻转后的链表。k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么将最后剩余节点保持原有顺序。 说明:

你需要自行定义链表结构,将输入的数据保存到你的链表中;你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换;你的算法只能使用常数的额外空间。 输入描述: 第一行输入是链表的值 第二行输入是K的值,K是大于或等于1的整数

输入形式为: 1 2 3 4 5 2

输出描述: 当 k = 2 时,应当输出: 2 1 4 3 5

当 k = 3 时,应当输出: 3 2 1 4 5

当k=6时,应当输出: 1 2 3 4 5

分析

写一个函数reverseGroup(head, k),不断向后取k个结点进行翻转,并把前面翻转好的尾结点与新取的k个结点翻转后的头结点链接,如果链表不足k个结点,则不做翻转。

写一个reverseList(head, tail)进行局部翻转,设置两个指针head, tail 分别指向当前k个结点的头结点和尾结点,翻转之后,head和tail则指向当前k的结点的尾结点和头结点。

分析草图如下图所示: 分析草图

代码 import java.util.Scanner; public class Main{ //定义链表数据结构 static class ListNode{ public int val; public ListNode next=null; public ListNode(int val){ this.val=val; } } public static ListNode reverseGroup(ListNode head, int k){ //先判断链表和k的合法性 if(head == null || head.next == null || k


【本文地址】


今日新闻


推荐新闻


CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3